package com.lw.leetcode.binary.a;

/**
 * 1351. 统计有序矩阵中的负数
 *
 * @Author liw
 * @Date 2021/5/23 13:09
 * @Version 1.0
 */
public class CountNegatives {


    public static void main(String[] args) {
        CountNegatives test = new CountNegatives();
        int[] arr = {-5, -6, -1, 0,- 5, -1};
        int i = test.find(arr, 0, 5);
        System.out.println(i);
    }

    public int countNegatives(int[][] grid) {

        int count = 0;

        int a = grid.length;
        int b = grid[0].length;
        int end = b - 1;
        for (int i = 0; i < a; i++) {
            int[] ints = grid[i];
            int value = find(ints, 0, end);
            if (ints[value] < 0) {
                count += (b - value);
                end = value - 1;
            } else {
                count += (b - value - 1);
                end = value;
            }

        }

        return count;
    }

    private int find(int[] arr, int st, int end) {
        while (st < end) {
            int m = st + ((end - st) >> 1);
            if (arr[m] < 0) {
                end = m;
            } else {
                st = m  + 1;
            }
        }
        return st;
    }

}
